NTRUSign

NTRUSign, также известный как NTRU Signature Algorithm, является ключевым алгоритмом шифрования с открытым ключом цифровой подписи на основе схемы подписи GGH.

История

Впервые алгоритм был представлен на сессии en:Asiacrypt 2001 года и опубликован в рецензируемой форме на конференции RSA 2003 года. Издание 2003 года включало рекомендации параметров для уровня безопасности 80 бит. В следующей публикации 2005 года были пересмотрены рекомендации для уровня безопасности 80 бит, а также представлены параметры востребованных уровней безопасности 112, 128, 160, 192 и 256 бит и описаны алгоритмы для получения наборов параметров для любого желаемого уровня безопасности. NTRU Cryptosystems, Inc. подали заявку на патент на данный алгоритм.^{[когда?]}

Особенности

NTRUSign включает в себя отображение сообщения для случайной точки в 2N-мерном пространстве, где N является одним из параметров NTRUSign, и решение проблемы нахождения ближайшего вектора в решётке, тесно связанной с решёткой NTRUEncrypt. Данная решётка обладает свойством: частный 2N-мерный базис для решётки можно описать с помощью 2-х векторов, каждый из которых состоит из N коэффициентов и базиса, который может быть определён отдельным N-размерным вектором. Это позволяет представлять открытые ключи в [math]\displaystyle{ O (N) }[/math] пространстве, а не [math]\displaystyle{ O (N^2) }[/math], как и в случае с другими схемами подписи на основе решёток. Операции занимают [math]\displaystyle{ O (N^2) }[/math] времени, в отличие от [math]\displaystyle{ O (N^3) }[/math] для криптографии на эллиптических кривых и RSA. Поэтому NTRUSign быстрее данных алгоритмов при низких уровнях безопасности и значительно быстрее при высоких уровнях безопасности.

NTRUSign находится в стадии рассмотрения по стандартизации рабочей группой IEEE P1363.

Описание алгоритма

Так же как и в NTRUEncrypt, в NTRUSign вычисления производятся в кольце [math]\displaystyle{ R = \Z_q[X]/(X^N-1) }[/math], где умножение „[math]\displaystyle{ * }[/math]“ является циклической сверткой по модулю [math]\displaystyle{ q }[/math]. Произведением двух полиномов [math]\displaystyle{ f = [f_0, f_1, \ldots, f_{N-1}] }[/math] и [math]\displaystyle{ g = [g_0, g_1, \ldots, g_{N-1}] }[/math] является [math]\displaystyle{ f*g = \sum_{i+j \equiv k \mod N}f_i \cdot g_j \mod q }[/math].

За основу NTRUSign могут быть взяты стандартные или транспонированные решетки. Основное преимущество транспонированной решетки заключается в том, что коэффициенты многочлена принадлежат {-1,0,1}. Это увеличивает скорость умножения.

Генерация ключа

• Входные данные: целые [math]\displaystyle{ N,q,d_f,d_g,B\gt 0 }[/math], строка [math]\displaystyle{ t = standard }[/math] или [math]\displaystyle{ transpose }[/math].
• Генерация [math]\displaystyle{ B }[/math] закрытых решёточных базисов и один открытый решеточный базис

Установить [math]\displaystyle{ i = B }[/math]. До тех пор, пока [math]\displaystyle{ i \gt 0 }[/math]:

1. Произвольно выбрать [math]\displaystyle{ f }[/math], [math]\displaystyle{ g }[/math] ∈ [math]\displaystyle{ \R }[/math], взаимно простые с [math]\displaystyle{ d_f }[/math], [math]\displaystyle{ d_g }[/math] соответственно.
2. Найти малые [math]\displaystyle{ F, G \in R }[/math] такие, что [math]\displaystyle{ f*G - F*g = q }[/math].
3. Если [math]\displaystyle{ t = standard }[/math], установить [math]\displaystyle{ f_i = f }[/math] и [math]\displaystyle{ f'_i = F }[/math].

Если [math]\displaystyle{ t = transpose }[/math], установить [math]\displaystyle{ f_i = f }[/math] и [math]\displaystyle{ f'_i = g }[/math].

Вычислить [math]\displaystyle{ h_i = f_i^{-1} * f'_i mod q }[/math]. Установить [math]\displaystyle{ i=i-1 }[/math].

• Публичный ключ: входные параметры и [math]\displaystyle{ h = ho = f_0^{-1} * f'_0 \operatorname{mod} q }[/math].
• Закрытый ключ: [math]\displaystyle{ \left\{ f_i, f'_i, h_i \right\} }[/math] для [math]\displaystyle{ i = 0... B }[/math].

Подпись

Подпись требует хеш-функцию [math]\displaystyle{ H: \mathcal{D} \rightarrow R }[/math] на цифровом пространстве документа [math]\displaystyle{ \mathcal{D} }[/math].

• Входные данные: цифровой документ [math]\displaystyle{ D \in \mathcal{D} }[/math] и закрытый ключ [math]\displaystyle{ \left\{ f_i, f'_i, h_i \right\} }[/math] для [math]\displaystyle{ i = 0... B }[/math].
• Установить [math]\displaystyle{ r = 0 }[/math].
• Установить [math]\displaystyle{ s = 0 }[/math] и [math]\displaystyle{ i = B }[/math]. Представить [math]\displaystyle{ r }[/math] как строку бит. Установить [math]\displaystyle{ m_o = H(D||r) }[/math], где [math]\displaystyle{ || }[/math] обозначает конкатенацию. Установить [math]\displaystyle{ m = m_o }[/math].

1. [math]\displaystyle{ \left\{ f_i, f'_i, h_i \right\} }[/math] - [math]\displaystyle{ i }[/math]-е основание
2. Вычислить [math]\displaystyle{ x = \lfloor -\frac{1}{q}m_i*f'_i \rceil }[/math]
3. Вычислить [math]\displaystyle{ y = \lfloor \frac{1}{q}m_i*f_i \rceil }[/math]
4. [math]\displaystyle{ s_i = x*f + y*f' }[/math]
5. [math]\displaystyle{ m_i = si*(h_i-h_{i-1}) \mod q }[/math]
6. Подпись: [math]\displaystyle{ s = s + s_i }[/math]

Проверка подписи

Верификация требует такую же хеш-функцию [math]\displaystyle{ H }[/math], «нормирующую связь» [math]\displaystyle{ \mathcal{N} \in \R }[/math] и норму полинома [math]\displaystyle{ ||.|| }[/math]. Норма [math]\displaystyle{ ||t|| }[/math] полинома [math]\displaystyle{ t }[/math] определяется как [math]\displaystyle{ \inf_{0 \leq k\lt q} ||t+kq||_z }[/math], где [math]\displaystyle{ ||r||_z = \sum_{i=0}^{N-1}r_i^2 - \frac{1}{N}\sum_{i=0}^{N}r_i }[/math] (где последнее - евклидова норма).

• Входные данные: Подписанные данные [math]\displaystyle{ (D,r,s) }[/math] и публичный ключ [math]\displaystyle{ h }[/math].
• Представить r как строку бит. Установить [math]\displaystyle{ m = H(D||r) }[/math].
• Вычислить [math]\displaystyle{ b = ||(s,s * h - m \operatorname{mod} g))|| }[/math].
• подпись считается верной, если [math]\displaystyle{ b \lt \mathcal{N} }[/math].

Замечание

• Рекомендуемые параметры [math]\displaystyle{ (N,q,d_f,d_g,B,t,\mathcal{N})=(251,128,73,71,1,transpose,310) }[/math]

Ссылки

• Most recent NTRUSign paper, including parameter sets for multiple security levels
• A Java implementation of NTRUSign Архивная копия от 23 декабря 2015 на Wayback Machine